1. Field of the Invention (Technical Field)
The present invention relates to methods for partitioning graphs, including those to balance the workload of parallel computers, and those used to optimize the placement of circuits on an integrated circuit.
2. Background Art
A fundamental problem arising in both parallel computing and in circuit design is that of partitioning a graph into nearly equally sized sets of vertices such that the number of edges crossing between sets is small. The method of graph construction and the specific cost associated with cross-edges will necessarily vary with the application, but the essential underlying problem of partitioning the graph is common to both of these and many other scientific and engineering applications.
In the parallel computing context, the graph partitioning problem arises as presently described. In order to perform a computation on most parallel computers, the problem must be divided into pieces which are assigned to difference processors. A partitioning must have two specific properties to enable an efficient computation. First, a roughly equal amount of work must be assigned to each processor. Second, the quantity of information transmitted between processors must be kept small. The problem of finding a partitioning with theses properties can be phrased naturally in terms of a graph. The graph G=(V,E) consists of a set of vertices V, each of which corresponds to some unit computation, and a set of edges E which connect two vertices if the computation corresponding to one needs input from the other. The problem is now to partition the vertices of the graph into P sets of roughly equal cardinality such that the number of edges crossing between sets is small. Solving this problem optimally is known to be difficult, i.e., it is NP-complete. In the more general case, the vertices and edges are assigned relative weights to allow for more subtle modeling of the computation, and the problem becomes that of partitioning the graph such that the total of vertex weights assigned to each set is roughly equal and that the cumulative weight of edges crossing between sets is minimal.
The same graph partitioning problem arises in Very Large Scale Integration (VLSI) circuit layout. Here the circuit is typically modeled as a graph in which vertices represent circuit components and an edge connects any two vertices that are in the same net list. The objective is to place the circuit elements on a chip so as to minimize the total wiring length subject to a variety of engineering constraints on component area, wire routing, etc. Relative component areas may De represented in the general case by vertex weights, and the goal is to place the components on a chip in such a way as to minimize the chip area consumed. The standard way to address this problem is a divide-and-conquer approach in which the graph is partitioned to generate smaller subproblems.
Most previous methods for graph partitioning work by recursive bisection. The graph is halved, the halves are halved and so on. This is a convenient simplification because it reduces the problem of dividing a graph into a large number of pieces (any power of two) to the problem of dividing it into just two pieces. Unfortunately, it results in suboptimal results. For instance, in the circuit layout problem, the first cut may determine which circuit elements will be placed in the top half of the chip and which in the bottom half. Dividing these two halves now determines which elements go into which quadrant of the chip. Unfortunately, since the halves are treated in isolation, this approach ignores the fact that a wire going from the lower left to the upper right is longer than one going from the lower left to the upper left. A similar problem arises in parallel computation. Because of the possibility of message congestion, the number of paths a message must be routed through is a good measure of the cost of the message, but a bisection approach cannot account for this effect.
In either the parallel computing or circuit layout setting, bisection can lead to problems because of its inability to plan ahead. In the circuit layout problem, a better approach would be to divide into four sets at once, explicitly accounting for the different wire lengths between different sets. In parallel computing, it would be best to divide into as many sets at one time as possible, including architectural distance in the optimization metric.
The present invention is of a method to divide a graph into four, eight or sixteen sets at once that incorporates a Manhattan metric between sets. This is precisely the correct metric for circuit layouts since wires are laid down in the horizontal or vertical directions. It is also the correct metric for hypercube or mesh architecture parallel computers due to the possibility of message congestion. Consequently, it produces better mappings to processors than methods based upon bisection strategies.
The prior art approach is known as "spectral bisection", in which an eigenvector of the Laplacian matrix of the graph is used to bisect a graph. See H. Simon, "Partitioning of unstructured problems for parallel processing", in Proc. Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications, Pergammon Press, 1991. Through a novel use of additional eigenvectors, the present invention can divide the graph into four, eight or sixteen pieces using two, three or four eigenvectors respectively. This induces a substantial increase in the complexity of the method, but results in significantly better answers than achievable with spectral bisection.
Previous efforts to divide into more than two sets at once have appeared in the literature. For circuit layouts, a quadrisection method based on locally swapping circuit elements is described in P. Suaris and G. Kedem, "An algorithm for quadrisection and its application to standard cell placement", IEEE Trans. Circuits and Systems, 35 (1988), pp. 294-303. A method that uses the eigenvectors of a different matrix to divide a graph into an arbitrary number of sets is described in F. Rendl and H. Wolkowicz, "A projection technique for partitioning the nodes of a graph", Tech Rep. CORR 90-20, University of Waterloo, Faculty of Mathematics, Waterloo, Ontario, November 1990. However, this method requires 2.sup.k eigenvectors to divide into 2.sup.k sets, whereas the present invention requires only k. Since the calculation of eigenvectors is the dominant computational step in spectral methods, the present approach is much more efficient. In addition, the method of Rendl et al. is unable to account for the notion of different distances between sets. This notion is of central importance in the parallel computing and circuit layout problems.